package com.dong.ch02_array;

import java.util.Stack;

/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class S020_brace {
    public static void main(String[] args) {
        String testStr = "([)]";
        S020_brace s020_brace = new S020_brace();
        System.out.println(s020_brace.isValid2(testStr));
    }
    public boolean isValid(String s) {
       // MyStack.StackArr<Character> stack = new MyStack.StackArr<>(s.length());
        Stack<Character> stack =new Stack();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char currentChar = chars[i];
            switch (currentChar) {
                case '(': stack.push(currentChar); break;
                case '[': stack.push(currentChar); break;
                case '{': stack.push(currentChar); break;
                case ')': {
                    if(stack.isEmpty()) {return false;}
                    if(stack.pop()!='('){return false;}
                    break;
                }
                case ']': {
                    if(stack.isEmpty()) {return false;}
                    if(stack.pop()!='['){return false;}
                    break;
                }
                case '}': {
                    if(stack.isEmpty()) {return false;}
                    if(stack.pop()!='{'){return false;}
                    break;
                }
                default: return false;
            }
        }
        return stack.isEmpty();
    }
    public boolean isValid2(String s) {
        int left = 0;
        char[] chars = s.toCharArray();
        //需要跳过的位置
        boolean[] hasVerified = new boolean[chars.length];
        for (int i = 0; i < chars.length; i++) {
            char currentChar = chars[i];
            switch (currentChar) {
                case '(':  break;
                case '[': break;
                case '{':   break;
                case ')': {
                    while(hasVerified[left]) {
                        left++;
                    }
                    if (chars[left]=='(') {
                        hasVerified[i]=true;
                        left++;
                        break;
                    }else {
                        return false;
                    }
                }
                case ']': {
                    while(hasVerified[left]) {
                        left++;
                    }
                    if (chars[left]=='[') {
                        hasVerified[i]=true;
                        left++;
                        break;
                    }else {
                        return false;
                    }
                }
                case '}': {
                    while(hasVerified[left]) {
                        left++;
                    }
                    if (chars[left]=='{') {
                        hasVerified[i]=true;
                        left++;
                        break;
                    }else {
                        return false;
                    }
                }
                default: return false;
            }
        }
        while(hasVerified[left]&&left<chars.length-1) {
            left++;
        }
        return left>=chars.length-1;
    }
}
